﻿using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System;
namespace songeP
{

    public class QuadTree
    {
        public static int max_objects = 4;
        public static int max_levels = 50;

        int level;
        List<Vector2> objects;
        Rect bounds;
        QuadTree[] nodes;

        /// <summary>是否分裂过</summary>
        bool isSplited = false;

        public QuadTree(int level, Rect bounds)
        {
            this.level = level;
            this.bounds = bounds;
            objects = new List<Vector2>();
            nodes = new QuadTree[4];
        }

        public void split()
        {
            isSplited = true;
            float subWidth = bounds.width / 2;
            float subHeight = bounds.height / 2;
            float x = bounds.x;
            float y = bounds.y;
            nodes[0] = new QuadTree(level + 1, new Rect(x, y, subWidth, subHeight));
            nodes[1] = new QuadTree(level + 1, new Rect(x + subWidth, y, subWidth, subHeight));
            nodes[2] = new QuadTree(level + 1, new Rect(x, y + subHeight, subWidth, subHeight));
            nodes[3] = new QuadTree(level + 1, new Rect(x + subWidth, y + subHeight, subWidth, subHeight));
        }

        int getIndex(Vector2 pos)
        {
            for (int i = 0; i < 4; i++)
            {
                if (nodes[i].bounds.Contains(pos))
                    return i;
            }
            return -1;
        }

        public int insert(Vector2 pos)
        {
            int newLevel = -1;
            if (isSplited)
            {
                int index = getIndex(pos);
                if (index != -1)
                {
                    newLevel = nodes[index].insert(pos);
                }
            }
            else
            {
                objects.Add(pos);
                newLevel = level;
                //超过容量max_objects, 分裂子空间, 并将全部对象分别放入子树
                if (objects.Count > max_objects && level < max_levels)//level > max_levels?
                {
                    split();

                    for (int i = objects.Count - 1; i >= 0; i--)
                    {
                        int index = getIndex(objects[i]);
                        if (index != -1)
                        {
                            nodes[index].insert(objects[i]);
                            newLevel = nodes[index].level;
                            objects.RemoveAt(i);
                        }
                    }
                }
            }
            return newLevel;
        }

        public List<Vector2> retrieve(Vector2 pos)
        {
            Debug.Log("retrieve-level:" + level);
            List<Vector2> result = new List<Vector2>();
            if (isSplited)
            {
                int index = getIndex(pos);
                if (index != -1)
                {
                    result.AddRange(nodes[index].retrieve(pos));
                }
            }
            result.AddRange(objects);
            return result;
        }

        /// <summary>结点移动后刷新树</summary>
        public void RefreshTree(QuadTree root = null)
        {
            if (root == null)
                root = this;
            if (isSplited)
            {
                foreach (QuadTree tree in nodes)
                {
                    tree.RefreshTree(root);
                }
            }
            else
            {
                objects.ForEach(p =>
                {
                    if (!bounds.Contains(p))
                    {
                        objects.Remove(p);//CHECK 此处删除结点是否会导致该Tree成为无结点的Tree?
                        root.insert(p);
                    }
                });
            }
        }

        public void forEachCallback(Action<Vector2, int> callback)
        {
            if (isSplited)
            {
                foreach (QuadTree tree in nodes)
                {
                    tree.forEachCallback(callback);
                }
            }
            else
            {
                foreach (Vector2 p in objects)
                {
                    callback(p, level);
                }
            }
        }
    }

}